package graph;

import com.sun.xml.internal.bind.v2.schemagen.xmlschema.Union;

import java.util.*;

/**
 * 邻接矩阵
 */
public class GraphByMatrix {
    private char[] arrayV;//顶点数组
    private int[][] matrix;
    private boolean isDirect;

    /**
     * @param size   顶点个数
     * @param Direct 是否是有向图
     */
    public GraphByMatrix(int size, boolean Direct) {
        arrayV = new char[size];
        matrix = new int[size][size];
        //使得二维数组矩阵用无穷大来进行初始化
        for (int i = 0; i < matrix.length; i++) {
            Arrays.fill(matrix[i], Integer.MAX_VALUE);
        }
        this.isDirect = Direct;
    }

    public void initArrayV(char[] array) {
        for (int i = 0; i < arrayV.length; i++) {
            arrayV[i] = array[i];
        }
    }

    /**
     * @param srcV   起点
     * @param destV  终点
     * @param weight 权重
     */
    public void addEdge(char srcV, char destV, int weight) {
        int srcVIndex = getIndexOfV(srcV);
        int destVIndex = getIndexOfV(destV);
        matrix[srcVIndex][destVIndex] = weight;
        //判断是不是无向图
        //因为无向图的邻接矩阵对称
        if (!isDirect) {
            matrix[destVIndex][srcVIndex] = weight;
        }
    }

    private int getIndexOfV(char v) {
        for (int i = 0; i < arrayV[i]; i++) {
            if (v == arrayV[i]) {
                return i;
            }
        }
        return -1;
    }


    public void printGraph() {
        for (int i = 0; i < arrayV.length; i++) {
            System.out.print(arrayV[i] + " ");
        }
        System.out.println();
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if (matrix[i][j] == Integer.MAX_VALUE) {
                    System.out.print("∞ ");
                } else {
                    System.out.print(matrix[i][j] + " ");
                }
            }
            System.out.println();
        }
    }

    /**
     * 获取顶点的度
     *
     * @param v
     * @return
     */
    public int getDevOfV(char v) {
        int count = 0;
        int index = getIndexOfV(v);
        for (int i = 0; i < matrix[index].length; i++) {
            if (matrix[index][i] != Integer.MAX_VALUE) {
                count++;
            }
        }
        //判断是不是有向图,有向图顶点的度包括入度和出度
        if (isDirect) {
            for (int i = 0; i < matrix.length; i++) {
                if (matrix[i][index] != Integer.MAX_VALUE) {
                    count++;
                }
            }
        }
        return count;
    }

    /**
     * 广度优先遍历
     *
     * @param v
     */
    public void bfs(char v) {
        //得到起点的坐标
        int src = getIndexOfV(v);
        //标记是否出现过
        boolean[] visited = new boolean[arrayV.length];
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(src);
        while (!queue.isEmpty()) {
            int top = queue.poll();
            System.out.print("->" + arrayV[top]);
            //弹出置为true
            visited[top] = true;
            for (int i = 0; i < arrayV.length; i++) {
                if (matrix[top][i] != Integer.MAX_VALUE && !visited[i]) {
                    queue.offer(i);
                    visited[i] = true;
                }
            }
        }
    }

    /**
     * 深度优先遍历
     *
     * @param v
     */
    public void dfs(char v) {
        //得到起始位置
        int index = getIndexOfV(v);
        boolean[] visited = new boolean[arrayV.length];

        dfsChild(index, visited);
    }

    private void dfsChild(int index, boolean[] visited) {
        System.out.print(arrayV[index] + "->");
        visited[index] = true;
        for (int i = 0; i < arrayV.length; i++) {
            if (matrix[index][i] != Integer.MAX_VALUE && !visited[i]) {
                dfsChild(i, visited);
            }
        }

    }

    /**
     * 抽象出边
     */
    static class Edge {
        public int srcIndex;
        public int destIndex;
        public int weight;

        public Edge(int srcIndex, int destIndex, int weight) {
            this.srcIndex = srcIndex;
            this.destIndex = destIndex;
            this.weight = weight;
        }
    }

    /**
     * 克鲁斯卡尔算法
     * @param minTree 最小生成树
     * @return
     */
    public int kruskal(GraphByMatrix minTree) {
        //存储边
        PriorityQueue<Edge> p = new PriorityQueue<>(new Comparator<Edge>() {
            @Override
            public int compare(Edge o1, Edge o2) {
                return o1.weight - o2.weight;
            }
        });
        //遍历邻接矩阵,放入优先级队列
        int n = arrayV.length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if(i<j) {
                    p.offer(new Edge(i,j,matrix[i][j]));
                }
            }
        }

        return 0;
    }
    public static void main(String[] args) {

        GraphByMatrix graph = new GraphByMatrix(4, true);
        char[] array = {'A', 'B', 'C', 'D'};
        graph.initArrayV(array);

        graph.addEdge('A', 'B', 1);
        graph.addEdge('A', 'D', 1);
        graph.addEdge('B', 'A', 1);
        graph.addEdge('B', 'C', 1);
        graph.addEdge('C', 'B', 1);
        graph.addEdge('C', 'D', 1);
        graph.addEdge('D', 'A', 1);
        graph.addEdge('D', 'C', 1);
        graph.dfs('B');
       /* System.out.println();
        graph.printGraph();
        System.out.println(graph.getDevOfV('A'));*/
    }
}
